package com.zx._12_算法.剑指offer._2022;

import com.zx._12_算法.TreeNode;


/**
 * https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof
 *
 * 二叉搜索树概念：https://baike.baidu.com/item/二叉搜索树/7077855?fr=aladdin
 *
 * 解法基于此性质：二叉搜索树的中序遍历为 递增序列。所以，得出二叉搜索树的 中序遍历倒序 为 递减序列
 *
 * 因此，求 “二叉搜索树第 k大的节点” 可转化为求 “此树的中序遍历倒序的第 k个节点”。
 */
public class 二叉搜索树的第k大节点 {

    int res = 0;
    int k = 0;

    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        this.res = 0;

        find(root);

        return this.res;
    }

    private void find(TreeNode root) {
        // 右中左
        if (root == null) {
            return;
        }

        find(root.right);

        k--;
        if (k == 0) {
            res = root.val;
            return;
        }

        find(root.left);

    }

}
